/**
 * Copyright (C), 2018-2018
 * FileName: wuChongFuSanWeiShu  * Author:   lcsos
 * Date:     2018/10/17 21:57
 * Description:
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.qdu.study.arithmetic.second;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>  
 *  题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？
 *  程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。
 * @author Lcs
 * @create 2018/10/17 
 * @since 1.0.0
 */

public class wuChongFuSanWeiShu {
    /**
     * 功能描述: <br>
     * 〈〉
     *  第一种算法，直接算法
     *  重用性很低，如果计算的位数越高，所嵌套的循环层数越多，这样会导致程序的复杂度增高
     * @since: 1.0.0
     * @Author:Lcs
     * @Date: 2018/10/17 22:14
     */

    private static void demo1(){
        //用于计数多少种
        int num = 0;
        //将所有的组合方式都排序一遍
        for(int i = 1;i <= 4;i++){
            for(int j = 1;j <= 4;j++){
                for(int k = 1;k <= 4;k++){
                    //只选择不重复的排序
                    if(i!=j&j!=k&i!=k){
                        num++;
                        System.out.println(i*100+j*10+k);
                    }
                }

            }
        }
        System.out.println("一共有"+num+"中排列组合");
    }

    /**
     *
     * @param x 当前的取第几位
     * @param a 取出n位数组
     * @param b 选取参数的数组（这里可以优化的，可以用list类里面去掉一个参数，那么递归的效率会提高）
     * @since: 1.0.0
     * @Author:Lcs
     * @Date: 2018/10/17 25:20
     */
    private static void demo2(int x,int[] a,int[] b){
        //设置跳出递归的条件
        if(x<a.length){
            for(int i=0;i<b.length;i++){
                int j=0;
                boolean f = true;
                while(j<x){
                    if(a[j]==b[i]){
                        f=false;
                        break;
                    }
                    j++;
                }
                a[x]=b[i];
                if(f&&x==a.length-1){
                    //输出所有的组合，也可以用一个参数接收，自己定义
                    System.out.println(Arrays.toString(a));
                }
                //如果不是最后一位，那么继续递归去取数
                else if(f){
                    demo2(x+1,a,b);
                }
            }
        }
    }
    public static void main(String[] args) {

//        //调用第一种算法
//        demo1();

        //调用第二种算法

        int[] a = {1,2,3,4};
        int n = 3;
        //取出n位不同的数字，就能保证位置上不重复,
        //题目中没有限制n的大小，最好的方式用递归
        demo2(0,new int[n],a);
    }
}
